package com.wfm.leetcode.editor.cn;

import java.util.Arrays;

/**
 * 下一个排列
 * 2025-02-12 18:00:10
 *
 * 从后向前 查找第一个 相邻升序 的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
 * 在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
 * 将 A[i] 与 A[k] 交换
 * 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
 * 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
 *
 *
 *
 */
class NextPermutation {

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length<=1) return;
        int i = nums.length-2,j=nums.length-1,k=nums.length-1;
        // 找到ij
        while(i>=0&&nums[i]>=nums[j]){
            i--;
            j--;
        }
        if(i>=0){ // 说明不是最后一个排列， 即54321这种，这种直接跳到下面翻转就行了
            // 在降序序列里找到第一个大于i的k
            while(nums[i]>=nums[k]){
                k--;
            }
            // 交换
            int temp = nums[i];
            nums[i] = nums[k];
            nums[k] = temp;
        }
        // reverse A[j..end]
        for (int m = j,n=nums.length-1; m < n; m++,n--) {
            // 交换
            int temp = nums[m];
            nums[m] = nums[n];
            nums[n] = temp;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new NextPermutation().new Solution();
        int[] nums = {1,2,3};
        solution.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
        
    }
}